The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.
Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.
In [2]:
from time import time
start = time()
from sympy import primerange, isprime
primes = list(primerange(2, 50000))
N = len(primes)
minsum = 1e100
def concat(p, q):
return int(f'{p}{q}')
def edge(p, q):
if (p,q) in E:
return E[p,q]
answer = isprime(concat(p,q)) and isprime(concat(q,p))
E[p,q] = answer
return answer
cliques = [([], 0)]
for p in primes:
E = {}
if p >= minsum:
break
new_cliques = []
for clique, weight in cliques:
if all(edge(p,q) for q in clique):
new_clique = clique + [p]
if len(new_clique) == 5:
minsum = min(minsum, weight + p)
new_cliques.append((new_clique, weight + p))
cliques.extend(new_cliques)
print(minsum)
print("Time: %.2f seconds" % (time() - start))
In [ ]: